package pfq.demo.algorithm.linkedlist;

/**
 * 链表的基础操作
 * 1. 定义
 * 2. 遍历
 * 3. 删除
 * 4. 插入（插头、插尾、插前、插后）
 * 5. 反转
 */

/**
 * 定义链表中的一个结点
 */
class Node {
    public int value;// 数据
    public Node next;// 下一个结点

    public Node(int value, Node next) {
        this.value = value;
        this.next = next;
    }
}

public class SinglyLinkedList {
    private Node head = null;

    // 插到链尾
    public void add2Tail(int value) {
        Node node = new Node(value, null);

        // 链表为空
        if (head == null) {
            head = node;
        } else {
            // 链表不为空，插到链尾
            Node temp = head;
            while (temp.next != null) {
                temp = temp.next;
            }
            temp.next = node;
        }
    }

    // 插到链头
    public void add2Head(int value) {
        Node node = new Node(value, null);
        // 链表为空
        if (head == null) {
            head = node;
        } else {
            // 链表不为空，插到链头
            node.next = head;
            head = node;
        }
    }

    // 插到某结点之前
    public void addBefore(int value, Node node) {
        // 要插入哪个结点，这个结点当然不能是null了
        if (node == null) return;

        // 空链表
        if (head == null) {
            add2Head(value);
            return;
        }

        Node temp = head;
        // 遍历找到要插入结点的前驱结点
        while (temp != null && temp.next != node) {
            temp = temp.next;
        }

        // 在链表中没有找到要插入的这个结点
        if (temp == null) return;

        node.next = temp.next;
        temp.next = node;


    }

    // 插到某结点之后
    public void addAfter(int value, Node node) {

        if (node == null) return;

        if (head == null) {
            add2Tail(value);
            return;
        }

        Node temp = head;
        while (temp != null && temp != node) {
            temp = temp.next;
        }

        if (temp == null) return;

        node.next = temp.next;
        temp.next = node;

    }

    public void delete(Node node) {
        if (head == null || node == null) return;

        // 要删除的结点正好是头结点
        if (node == head) {
            head = head.next;
            return;
        }

        Node temp = head;
        while (temp != null && temp.next != node) {
            temp = temp.next;
        }

        if (temp == null) return;

        temp.next = temp.next.next;
    }

    /**
     * 遍历链表
     */
    public void printAll() {
        if (head == null) {
            System.out.println("链表为空");
            return;
        }
        StringBuilder sb = new StringBuilder("链表：");
        Node node = head;
        while (node != null) {
            sb.append(node.value);
            sb.append(", ");
            node = node.next;
        }

        System.out.println(sb.toString());
    }

    /**
     * 链表反转
     * 头插法：
     * 1. 将当前结点的next指向其的前驱结点
     * 2. 操作1之前，要先将当前结点的next保存下
     */
    public void reverse() {
        if (head == null) return;

        Node curr = head;
        Node prev = null;

        while (curr != null) {
            Node next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        head = prev;
    }

    public static void main(String[] args) {

        int[] data = {2, 3, 1, 4, 6};

        SinglyLinkedList linkedList = new SinglyLinkedList();
        linkedList.printAll();

        for (int value : data) {
            linkedList.add2Tail(value);
        }

        linkedList.printAll();
        linkedList.reverse();
        linkedList.printAll();

    }
}


